概述

排序算法的划分可以从几个不同的维度进行划分

时间复杂度

1. 平方阶 $O(n^2)$： 各类简单排序：直接插入、直接选择和冒泡排序。
2. 线性对数阶 $O(nlog(n^2))$： 快速排序、堆排序、希尔排序和归并排序
3. 线性阶 $O(n)$： 基数排序，此外还有桶、箱排序。

空间维度

如果要分析排序算法占用多少内存，是否需要外存就能完成排序等，可以分为以下几种排序

• 内部排序：若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序。
• 外部排序：若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，则称此类排序问题为外部排序。
• 就地排序：若排序算法所需的辅助空间并不依赖于问题的规模 n，即辅助空间为 O（1），称为就地排序。

与其说用内部排序和外部排序来划分不同的排序算法，不如说内外排序是不同的算法策略

• 内部排序在加载数组进内存后，使用一种排序算法进行排序即可完成
• 而外部排序通常采用排序-归并，将指定大小的数据（如 100M）加载进内存，使用内排中的某种排序算法（如快速排序、堆排序、归并排序等方法）在内存中完成排序，再讲排序完成的数据写入磁盘。不断重复上述过程，完成所有数据排序之后，对外存中排序好的数据进行归并处理。关于外部排序的详细描述，可以查看wiki

而就地排序则是针对排序算法是否需要使用额外辅助空间，常见排序算法的划分如下：

1. 就地排序：冒泡排序、选择排序、插入排序、希尔排序、快速排序（如果不考虑递归函数空间的话）
2. 非就地排序：堆排序、归并排序、桶排序、基数排序

元素相对位置

稳定排序：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序后，这些记录的相对次序保持不变，即在原序列中 ri=rj， ri 在 rj 之前，而在排序后的序列中，ri 仍在 rj 之前，则称这种排序算法是稳定的；否则称为不稳定的。

1. 稳定：冒泡排序、插入排序、归并排序和基数排序。

2. 非稳定：选择排序、快速排序、希尔排序、堆排序。

冒泡排序、快速排序

冒泡通常在 CS 课程中会当做第一个排序算法介绍给同学，毕竟也算是最基础的排序算法。

至于为什么要将冒泡和快排放一个章节，因为快排可以看做是冒泡的一个优化方案，具体下文会详细描述

2.1 冒泡排序

英文名称是 bubble sort

已知一组无序数据 a[0]、a[1]、……a[n-1]，需将其用冒泡排序按升序排列。

首先比较 a[0]与 a[1]的值，若 a[0]大于 a[1]则交换两者的值，否则不变。再比较 a[1]与 a[2]的值，若 a[1]大于 a[2]，则交换两者的值，否则不变。以此类推。。。最后比较 a[n-2]与 a[n-1]的值。这样处理一轮后，a[n-1]的值一定是这组数据中最大的。

再对 a[0]~a[n-2]以相同方法处理一轮，则 a[n-2]的值一定是 a[0]~a[n-2]中最大的。以此类推。。。

这样共处理 n-1 轮后 a[0]、a[1]、……a[n-1]就以升序排列了。

Example
待排序列    3    2    5    9    2

第一轮

第1次比较  2    3    5    9     2

第2次比较  2    3    5    9     2

第3次比较  2    3    5    9     2

第4次比较  2    3    5    2  |  9

第二轮

第5次比较  2    3    5     2    9

第6次比较  2    3    5     2    9

第7次比较  2    3    2  |  5    9

第三轮

第8次比较  2    3     2    5    9

第9次比较  2    2  |  3    5    9

第四轮

第10次比较  2  |  2    3   5    9

以上分割线左侧为下一轮的待排序序列，右侧为已排序好的序列。

可以看到 5 个关键码组成的序列，经过 4 轮共计 10 次比较，比较次数是不变的，比较次数公式为：

$n*(n-1)/2$

动画演示

算法评价

优点：如果你不是故意去交换相等的关键码的话，这个算法是绝对稳定的排序算法。

缺点：比较次数也就是所谓的时间复杂度 为$O(n^2)$，最好的情况和最坏的情况都是$O(n^2)$

从上面例子中，我们可以看到第一、二、三轮，2 和 3 两个关键码重复比较了 3 次，很显然这不是令人满意的，那么如何解决这个问题呢？答案是快速排序

事实上，虽然冒泡排序是最基本的经典算法，但现实中基本都使用快速排序，基本没有使用冒泡排序的 scene 了

代码实现

const bubbleSort = (arr) => {
  for (let i = 0; i < arr.length - 1; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[i]) {
        ;[arr[i], arr[j]] = [arr[j], arr[i]]
      }
    }
  }
  return arr
}

2.2 快速排序

快速排序（Quicksort）是对冒泡排序的一种改进。

快速排序由 Hoare 在 1962 年提出，以下是这位计算机科学家的大头照，是一位和蔼可亲的老头，哎，还是个秃子，不过对搞计算机的人来说，这并不足为奇！

快速排序的基本思想

1. 通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小。（Partition）
2. 然后再按此方法对这其中一部分数据进行快速排序，这是递归调用。
3. 再按此方法对另一部分数据进行快速排序，这也是递归调用。

其中，Partition 的思想非常有用，划分左右区间，分别满足不同的条件，在很多题目中可以利用 partition 做到快排的变种，下面给出的题目中可以看到

算法介绍

设要排序的数组是 A[0]……A[n-1]

首先任意选取一个数据作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序。

一趟快速排序算法

1. 设置两个变量 i、j，排序开始的时候：i=0，j=n-1；
2. 以第一个数组元素作为关键数据，赋值给 pivot，即 pivot =A[0]；
3. 从 j 开始向前搜索，即由后开始向前搜索(j--)，找到第一个小于 pivot 的值 A[j]，将 A[j] 和 A[i] 互换（互换保证了 A[j] < A[i]，也就是保证了要趋向于前方的关键码都小于 pivot )；
4. 从 i 开始向后搜索，即由前开始向后搜索(i++)，找到第一个大于 pivot 的 A[i]，将 A[i] 和 A[j] 互换（互换保证了 A[j] < A[i]，也就是保证了后方的关键码都大于 pivot ）
5. 重复第 3、4 步，直到 i=j 。
6. 完成本轮比较

Example
我们仍然以冒泡排序举的那个例子来模拟演示快速排序，待排序的序列为：

 3    2    5    9    2

第一轮比较，选取第一个关键码 3 为pivot，初始值 i =0,  j =4，如下图圈1所示，

A[j]=5 与 pivot 比较，因为后面的关键码 2 小，所以要与 pivot 交换，如圈 2 所示，大家注意看下，经过这一步操作，原来靠后的关键码 2 跑到了原先靠前的关键码 2 前方，所以快速排序不是稳定的排序算法。

该到移动 i 的时候了，等到圈 4 的时候，关键码 5 大于 pivot，需要交换，让 5 放在 pivot 的后面，因为 pivot 后面的要比它大吗，如圈 4 所示。

该到移动 j 的时候了，关键码 9 显然大于 pivot，如圈 5 所示，所以 j 继续向前移动。

j 此时已经与 i 重合了，所以 while 循环终止，至此完成了第一轮迭代。

可以看到 pivot 位置的变动，刚开始位于索引 0 处，然后又到最后位置，最后定格在索引 2 处。我们很幸运的是，经过本轮快排后，pivot=3 把排序区间划分的比较均匀，前面有 2 个元素，后面也有 2 个元素，这是理想的！后面，我们在分析快排的性能时会意识到这个幸运的重要性！

完成了第一轮迭代后，再就是对 pivot 前的区间再次执行上述操作，然后再对 pivot 后的区间也是执行上述操作。

整个快速排序完成。

快排和冒泡的直观比较

上面这个例子，快速排序第一轮经过了 5 次比较，2 次交换，使得 Pivot 将整个排序序列分割成两个独立的区间，前面都小于 Pivot，后面都大于 Pivot；前面区间只需要 1 次比较，0 次交换即可完成；后面区间只需要 1 次比较，1 次交换就可完成，因此总的比较次数为 7 次，交换次数为 3 次。

而同样冒泡排序呢，由上节我们知道它需要 10 次比较，4 次交换才能完成排序。

性能分析

最坏情况

快速排序的最坏情况，实际上就退化为了冒泡排序的情况，想想冒泡排序，每一轮比较后，都将原来的排序好的区间增加了一个长度，也就是说快速排序每次选择的 pivot 也正好达成了冒泡排序的作用，那么最坏情况就此发生。简单来说，最坏情况发生在每次划分过程产生的两个区间分别包含 n-1 个元素和 1 个元素的时候。那么不难知道，最坏情况的复杂度也为 $O(n^2)$。

最好情况

如果每次划分过程产生的区间大小都为 n/2，则快速排序法运行就快得多了，此时的时间复杂度为 $O（nlogn）$，logn 表示以 2 为底，n 的对数。因为每轮比较都会平均分成 2 个区间，共经过趋向于 n 轮的比较。

平均情况

平均情况和最好情况的时间复杂度都为$O（nlogn）$，只不过平均情况的常数因子可能大一些，有关详细分析，请查阅相关资料。

Cons

（1）快排是一个效率很高的排序算法，但是对于长度很小的序列，快排效率低。研究表明长度在 5~25 的数组，快排不如插入排序。

（2）pivot 选择不当，将导致树的不平衡，这样导致快排的时间复杂度为 o(n^2);

（3）但数组中有大量重复的元素，快排效率将非常之低。

动画演示

代码实现

const swap = (arr, a, b) => {
  arr[a] ^= arr[b]
  arr[b] ^= arr[a]
  arr[a] ^= arr[b]
}

const quickSort = (arr, start, end) => {
  if (start === end) {
    return arr
  }
  let pivot = start + ~~(Math.random() * (end - start + 1))
  swap(arr, pivot, start)
  pivot = start++
  let l = start,
    r = end
  while (l < r) {
    if (arr[l] <= arr[pivot]) {
      l++
      continue
    }
    if (arr[r] >= arr[pivot]) {
      r--
      continue
    }
    ;[arr[l], arr[r]] = [arr[r], arr[l]]
    l++
    r--
  }
  if (arr[l] > arr[pivot]) {
    l--
  }
  swap(arr, l, pivot)
  quickSort(arr, start, l - 1)
  quickSort(arr, l + 1, end)
  return arr
}

快速排序的再改进

对快速排序算法的改进主要从以下几个方面：

1. pivot 选取，我们随机取出来 3 个数，取中间大小的为基准值，使快排更稳定
2. 3-way partition：取三个变量切分数组，将数组分为大于，等于，小于基准元素三部分，这样在递归时就可以剔除相等的元素，减小比较的次数
3. 结合其他排序算法，短序列采用插入排序，长序列再采用快排

3-way-partition

关于快速排序的 double pointer 和 partition 思想，都是很值得借鉴和进一步利用的，例如 partition，我们还可以拓展一种情形：

先考虑这样一个问题，给定红、白、蓝三种颜色的小球若干个，将其排成一列，使相同颜色的小球相邻，三种颜色先后顺序为红，白，蓝。这就是经典的 Dutch national flag problem。

我们可以针对红，蓝，白三种颜色的球分别计数，然后根据计数结果来重新放球。不过如果我们将问题进一步抽象，也就是说将一个数组按照某个 target 值分为三部分，使得左边部分的值小于 target，中间部分等于 target，右边部分大于 target，这样就不能再用简单的计数来确定排序后的结果。这时候，就可以用到另一种 partition 算法：three-way-partition。它的思路稍微复杂一点，用三个指针将数组分为四个部分，通过一次扫描最终将数组分为 <，=，> 的三部分，如下图所示：

这里的主要思想就是在一遍扫描中，通过交换不同位置的数字，使得数组最终可以维持一定的顺序，和前面快排中用到的 partition 思想一致。区别在于快排按照 pivot 将数组分为两部分，左右部分中的值都可能等于 pivot，而 three-way-partition 将数组分为 <, =, >的三部分。

快速选择算法

考虑 Top K 问题

在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

示例 1:

输入: [3,2,1,5,6,4] 和 k = 2
输出: 5

对于Top K 问题，解法思路有：

1. 快速排序：排序完成后直接取第 k 个即可，但是容易想到，我们进行了多余的操作，因为不需要对每个元素进行排序，时间复杂度$O(nlog(n))$
2. 最小堆：维护一个大小为 k 的最小堆，从头开始遍历数组，扫描到值若大于堆顶则入队，然后删除堆顶。同样的，虽然相比快排，我们缩小了比较的大小（k），但是仍然进行了多余的比较，并且还要维护大小为 k 的堆，占用额外空间。时间复杂度为$O(nlog(k))$
3. 快速选择：为了排除掉多余的排序比较，我们可以考虑，其实我们需要的就是将数组划分为两个区间（partition），左边比指定元素（pivot）小，右边比 pivot 大，并且右边 partition 的大小为 k 即可，那么借助快排中 partition 的思想，随机取 pivot，我们进行一次 partition 后，可以得知 pivot 当前所属位置，如果小于 n-k，那么就要往右找，否则往左找。

换句话说，对于快速选择算法，其实就是在快排算法中，不对另外一半 partition 继续排序了，一旦找到 pivot 的位置等于 n-k，直接返回当前元素，从而避免了多余的比较。

相关题目

1. LeetCode 324. 摆动排序 II

题目要求给你一个整数数组 nums，将它重新排列成

nums[0] < nums[1] > nums[2] < nums[3]...

的顺序。

例如

Example 1

输入：nums = [1,5,1,1,6,4]
输出：[1,6,1,5,1,4]
解释：[1,4,1,5,1,6] 同样是符合题目要求的结果，可以被判题程序接受。

Example 2

输入：nums = [1,3,2,2,3,1]
输出：[2,3,1,3,1,2]

【解法一：快速排序】

想想其实思路不难，就是将数组排序，然后划分成等长的两个部分，我们假设为 L 和 R，然后依次从 L 和 R 中挑选最大元素，即可实现该题。

但是题目有个进阶要求：你能用 $O(n)$ 时间复杂度和 / 或原地 $O(1)$ 额外空间来实现吗？

Emmm，这仿佛就有点难度了，因为目前我们需要排序整个数组，算法复杂度分别为：

• 时间复杂度：$O(nlogn)$
• 空间复杂度：$O(n)$，生成 L 和 R 两个数组

那么，怎么优化呢？

【解法二：快速选择 + 3-way-partition】

在解法一的基础上，可以发现，其实我们并不关心 L 和 R 中的内部排序情况，只要 L 中的元素都比 R 中小即可，利用上文提及的快速选择并结合3-way-partition，可以有效的优化我们解法一，得到解法二

由于快速选择和 3-way-partition 的时间复杂度都为 $O(N)$，所以这一解法时间复杂度为 $O(N)$。和解法 1 相同，解法 2 也需要保存 A 数组和 B 数组，所以空间复杂度不变，仍为 $O(N)$

【解法三：解法二 + 虚地址】

虚地址需要利用 C++ 等其他语言的特性，这里就不再详细讨论，具体可以到LC 官方解答中查看

2. LeetCode 215. Kth Largest Element in an Array

即 Top-K 问题，在上文已详细讨论了解法，使用快速选择算法

3. 剑指 offer45.把数组排成最小的数

通过自定义比较函数，再进行快排

4. 移动零

本来可以利用上面第 3 题的思路，通过自定义比较函数，将 0 看作最大的数，同时其他数都一样大的想法，再进行快排进行处理，但是需要注意，题目要求维持数组中元素的相对次序，而快速排序是非稳定排序，因此不能维持相等元素相对次序，因此上述思路就行不通了，需要考虑使用稳定排序，可以采用第一章节列举的任一稳定排序算法

上述题目对应的总结在个人的LeetCode 总结中也有提及。

总结

要学会利用快排的双指针和 partition 思想，能处理很多题目，因此要融会贯通。但是快排是非稳定排序，不能保证相等元素的相对次序，需要注意

选择排序、堆排序

3.1 选择排序

直接选择排序，英文名称 ：Straight Select Sorting，是一个直接从未排序序列选择最值到已排序序列的过程。

基本思想

• 第一次从 R[0]~R[n-1]中选取最小值，与 R[0]交换；

• 第二次从 R[1]~R[n-1]中选取最小值，与 R[1]交换，....，

• 第 i 次从 R[i-1]~R[n-1]中选取最小值，与 R[i-1]交换，.....，

总共通过 n-1 次，得到一个按关键码从小到大排列的有序序列。

升序排序的例子

我们仍然用上节冒泡排序和快速排序举的例子。待排序列

3    2    5    9    2

演示如何用直接选择排序得到升序序列。

第一轮，从所有关键码中选择最小值与 R[0]交换，3 与 2 交换，如下图所示，

第二轮，从 R[1]~R[n-1]中选择最小值与 R[1]交换，3 与 2 交换；

第三轮，从 R[2]~R[n-1]中选择最小值与 R[2]交换，5 与 3 交换；

第四轮，从 R[3]~R[n-1]中选择最小值与 R[3]交换，9 与 5 交换；

终止。

算法评估

在直接选择排序中，共需要进行 n-1 轮，每轮必发生一次交换，每轮需要进行 n-i 次比较 $(1 \leq i \leq n-1)$，总的比较次数等于

$(n-1) + (n-2) + ... + ( n-(n-1) )$

化简后等于 $n + (n-1)(n-2)/2$

由此可知，直接选择排序的时间复杂度为 $O(n^2)$ ，空间复杂度为 $O(1)$ 。注意到，直接选择排序在最好和最坏情况下都是 $O(n^2)$。

一般地，排序算法的时间复杂度为 $O(n^2)$ 是不令人满意的排序算法，在选择排序算法的思想下，有一种选择排序算法提升了时间性能，它就是堆排序，接下来我们就看下堆排序。

3.2 堆排序

堆排序，英文名称 Heapsort，利用二叉树（堆）这种数据结构所设计的一种排序算法，是一种对直接选择排序的一种改建算法。在逻辑结构上是按照二叉树存储结构，正是这种结构优化了选择排序的性能，在物理存储上是连续的数组存储，它利用了数组的特点快速定位指定索引的元素。这么巧妙的算法又是哪位科学家发明的呢？

这个算法是计算机先驱奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德(Robert W．Floyd）和威廉姆斯(J．Williams）在 1964 年共同发明的堆排序算法，我们重点认识下弗洛伊德。

没错，就是这位，第一眼看上去是搞艺术创作的，没错他的确是在芝加哥大学读的文学，后来因为苦于找不上工作，改行去西屋电气公司当了二年计算机操作员，发现他对计算机非常感兴趣。

于是他下定决心要弄懂它，掌握它，于是他借了有关书籍资料在值班空闲时间刻苦学习钻研，有问题就虚心向程序员请教。白天不值班，他又回校去听讲有关课程，逐渐从计算机的门外汉变成计算机的行家里手。

1956 年他离开西屋电气公司，到芝加哥的装甲研究基金会（Armour Research Foundation），开始还是当操作员，后来就当了程序员。1962 年他被马萨诸塞州的 Computer Associates 公司聘为分析员。1965 年他应聘成为卡内基—梅隆大学的副教授，3 年后转至斯坦福大学，1970 年被聘任为教授。

之所以能这样快地步步高升，关键就在于弗洛伊德通过勤奋学习和深入研究，是一位自学成才的计算机科学家。

堆排序的基本概念

n 个关键字序列 $K_1，K_2，…，K_n$ 称为堆（Heap），当且仅当该序列满足如下性质：

$K_i \leq K_{2i + 1}$ 且 $K_i \leq K_{2i + 2} (0 \leq i \leq (n/2)-1)$，称为小根堆；

$K_i \geq K_{2i + 1}$ 且 $K_i \geq K_{2i+2} (1 \leq i \leq (n/2)-1)$， 称为大根堆。

说人话：所有父节点比左右子节点都大，就是大根堆；都小，就是小根堆

堆排序流程

堆排序算法涉及到的两个主要操作为，先构建一个初始堆，然后堆顶不断地和当前无序区的最后一个元素交换，交换可能会导致初始构建的大根堆不再是大根堆，所以需要再次调整堆（这个实际上还是构建一个初始堆的函数），简单来说：

1. 构建堆

2. 交换堆顶和无序区的最后一个元素，再次构建大根堆；

3. 重复步骤 2 的操作，直至无序区只剩下一个元素为止。

① 构建最大/小堆

从上往下构建（即不断插入构建）流程：

新插入的元素不断与父节点进行比较，如果比父节点大，就与父节点进行交换，直到不能交换为止

从上往下的构建原理比较清晰，就不做过多叙述。下面我们来看看从下往上的构建方法

从下往上构建流程：

从下往上构建，意味着二叉树结构已经插入了$n$个节点，但是不满足最大/小堆特性，也可以使无序数组的存储形式，然后为了构建最大/小堆，需要按照以下流程构建

1. 从最后一个非叶子节点开始
2. 判断当前节点与左右子节点的最大/小值，是否需要与当前节点交换
3. 交换完成后，判断是否破坏了交换的子堆的最大/小堆属性，如果破坏了，不断向下进行交换调整，直到满足所有子树都是最大/小堆
4. 继续查找下一个非叶子节点，重复步骤 1 到 3
5. 重复上述步骤，直到根节点交换后，结束最大/小堆构建

我们以下图为例，假设给定无序序列结构如下：

此时我们从最后一个非叶子结点开始（叶结点自然不用调整，第一个非叶子结点 $arr.length/2-1=5/2-1=1$，也就是下面的 6 结点），从左至右，从下至上进行调整。【9 下沉之后，9 变成了叶子节点，因此不会对子叶产生影响】

找到第二个非叶节点 4 【3/2 - 1 = 0】，由于[4,9,8]中 9 元素最大，4 和 9 交换。【4 下沉之后，变动了的子树必须重新调整】

这时，交换导致了子根[4,5,6]结构混乱，继续调整，[4,5,6]中 6 最大，交换 4 和 6

此时，我们就将一个无需序列构造成了一个大顶堆。

② 在构建好最大/小堆之后，我们便可以对其进行排序了

我们仍然用那个待排序列

3    2    5    9    2

首先我们按照上述方法构建最大堆，可以得到最大堆如下

下面开始第二步调整堆，也就是不断地交换堆顶节点和未排序区的最后一个元素，然后再构建大根堆，下面开始这步操作，交换栈顶元素 9（如上图所示）和未排序区的最后一个元素 2，如下图所示，现在排序区 9 成为了第一个归位的

接下来拿掉元素 9，未排序区变成了 2,3,5,2，然后从堆顶 2 开始进行堆的再构建，比较父节点 2 与左右子节点 3 和 5，父节点 2 和右孩子 5 交换位置，如下图所示，这样就再次得到了大根堆，

再交换堆顶 5 和未排序区的最后一个元素 2，这样 5 又就位了，这样未排序区变为了 2,3,2，已排序区为 5,9，交换后的位置又破坏了大根堆，已经不再是大根堆了，如下图所示，

所以需要再次调整，然后堆顶 2 和左孩子 3 交换，交换后的位置如下图所示，这样二叉树又重新变为了大根堆，再把堆顶 3 和此时最后一个元素也就是右孩子 2 交换，

接下来再构建堆，不再赘述，见下图。

算法评价

堆排序的时间，主要由建立初始堆和反复重建堆这两部分的时间开销构成，堆排序的平均时间复杂度是 O(nlogn) 。堆排序是就地排序，空间复杂度为 O(1）。

通过上面的例子，可以看到两个关键码 2 的相对位置会发生变化，所以堆排序是不稳定的排序方法。

代码实现

1. 从下往上，就地

// 堆排序
const swap = (A, a, b) => {
  A[a] ^= A[b]
  A[b] ^= A[a]
  A[a] ^= A[b]
}

const maxHeapify = (A, heapSize, i) => {
  let l = i * 2 + 1
  let r = i * 2 + 2
  let largest = i
  if (l < heapSize && A[l] > A[largest]) {
    largest = l
  }
  if (r < heapSize && A[r] > A[largest]) {
    largest = r
  }
  // 如果最大元素不是父节点，则交换
  if (largest !== i) {
    swap(A, i, largest)
    // 交换过后可能导致子树不再是最大堆，需要递归判断
    maxHeapify(A, heapSize, largest)
  }
}

const buildMaxHeap = (A, heapSize = A.length) => {
  for (let i = ~~(A.length / 2) - 1; i >= 0; i--) {
    maxHeapify(A, heapSize, i)
  }
}

const heapSort = (A) => {
  buildMaxHeap(A)
  let heapSize = A.length
  for (let i = A.length - 1; i >= 0; i--) {
    // 每次将 0 位置的最大元素交换到无序数组的最后一位
    swap(A, 0, i)
    maxHeapify(A, --heapSize, 0)
  }
  return A
}

2. 从上往下，插入

const swap = (A, a, b) => {
  const tmp = A[a]
  A[a] = A[b]
  A[b] = tmp
}

class MaxHeap {
  constructor(heapSize = Infinity) {
    this.heap = []
    this.heapSize = heapSize
  }

  maxHeapify(i) {
    const l = 2 * i + 1
    const r = 2 * i + 2
    let largest = i
    if (l < this.heapSize && this.heap[l] > this.heap[largest]) {
      largest = l
    }
    if (r < this.heapSize && this.heap[r] > this.heap[largest]) {
      largest = r
    }
    if (largest !== i) {
      swap(this.heap, i, largest)
      this.maxHeapify(largest) // 交换过后，子树可能不满足最大堆
    }
  }

  insert(node) {
    this.heap.push(node)
    let cur = this.heap.length - 1
    let parent = ~~((cur - 1) / 2)
    for (; cur > 0 && this.heap[parent] < this.heap[cur]; ) {
      swap(this.heap, cur, parent)
      cur = parent
      parent = ~~((cur - 1) / 2)
    }
    // 如果堆大小超出限制，需要pop一个
    if (this.size() > this.heapSize) {
      this.pop()
    }
  }

  pop() {
    swap(this.heap, 0, this.heap.length - 1)
    const ans = this.heap.pop()
    this.maxHeapify(0)
    return ans
  }

  size() {
    return this.heap.length
  }
}

const heapSort = (nums) => {
  const heap = new MaxHeap()
  for (let num of nums) {
    heap.insert(num)
  }
  const res = []
  while (heap.size()) {
    res.unshift(heap.pop())
  }
  return res
}

相关题目

以下题目是可以用堆排，但不仅限于用堆排。通常可以用堆排的题也可以用快排和桶排。

347. 前 K 个高频元素：给定一个非空的整数数组，返回其中出现频率前 k 高的元素。

692. 前 K 个高频单词：给一非空的单词列表，返回前 k 个出现次数最多的单词。

973. 最接近原点的 K 个点：有一个由平面上的点组成的列表 points。需要从中找出 K 个距离原点 (0, 0) 最近的点。

1167. 连接棒材的最低费用：会员题，可以用堆排。

插入排序、希尔排序

4.1 直接插入排序

直接插入排序，英文名称 straight insertion sort，它是一种依次将无序区的元素在有序区内找到合适位置依次插入的算法。

基本思想

每次从无序表中取出第一个元素，把它插入到有序表的合适位置，使有序表仍然有序，直到无序表内所有元素插入为止。

首先在当前有序区 R[0..i-1]中查找 R[i]的正确插入位置 k(0≤k≤i-1)；

然后将 R[k．．i-1]中的记录均后移一个位置，腾出 k 位置上的空间插入 R[i]。

直接插入排序举例

我们仍然用待排序列

3    2    5    9    2

演示直接插入排序的过程

至此结束插入排序的过程，可以看到直接插入排序共经过 4 轮的操作，有些轮需要经过找到元素的合适位置，同时移动插入点后元素到有序区元素依次向后移动一个位置，有些轮不需要移动数据元素，直接将待插入元素插入到有序区的最后一个位置。

算法评估

如果目标是把 n 个元素的序列升序排列，那么采用插入排序存在最好情况和最坏情况。

最好情况就是，序列已经是升序排列了，在这种情况下，需要进行的比较操作需（n-1）次即可。

最坏情况就是，序列是降序排列，那么此时需要进行的比较共有 $n(n-1)/2$ 次。

插入排序从上个演示中可以看到直接插入排序是稳定的排序算法，每次找到的插入点位置定下一个规则，要么统一放在相等关键码的前面或后面。

插入排序算法平均来说时间复杂度为 $O(n^2）$，比较次数越多，插入点后的数据移动越多（看下演示中的步骤 4），特别是当数据总量庞大的时候，但是可以用链表解决数据移动的问题。

因而，插入排序不适合对于数据量比较大的排序应用。直接插入排序在 n 不大时，插入排序的效果会很好，但是，如果需要排序的数据量很大直接插入排序的性能大幅下降，那么有没有优化的方法呢？由此诞生了插入思想下的希尔排序。

相关题目

147 对链表进行插入排序

4.2 希尔排序

由希尔在 1959 年提出，称为希尔排序(shell sort)，也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本。

希尔排序是基于直接插入排序的以下两点性质而提出改进方法的：

1. 直接插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率。就是上节提到的，最好情况就是，序列已经是升序排列了，在这种情况下，需要进行的比较操作需（n-1）次即可。

2. 直接插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位，如上节举的直接插入排序的例子，一轮只能操作一个数据。

希尔排序的关键概念---增量序列

是指在待排序序列中提取关键码所用的序号间隔，比如初始序列包含 5 个元素

[3 2 5 9 2]， 如果增量序列为 2，那么在一轮排序中，分为两组： [3 5 2] ，[2 9] ，在这两组中分别做直接插入排序。

算法流程

1. 先取一个正整数 d1 < n，把所有序号相隔 d1 的数组元素放一组，组内进行直接插入排序
2. 然后取 d2 < d1，重复上述分组和直接插入排序操作
3. 直至 di = 1，即所有记录放进一个组中排序为止

我们仍然用待排序列

3    2    5    9    2

进行非降序排序操作，一般的初次取序列的一半为增量，以后每次减半，直到增量为 1，

在第一轮中，选取增量为 2，即分为两组，第一组为 [3 5 2] ，另一组为 [2 9 ] ，分别对这两组做直接插入排序，第一组插入排序的结果为[2 3 5]，第二组不动，这样导致的直接结果是原来位于最后的 2 经过第一轮插入排序后，跑到最头里了，这样两个 2 的相对位置发生改变了，所以希尔排序不是稳定的排序算法。

再经过第二轮排序，此时的增量为 1，所以一共只有一组了，相当于直接插入排序，9 后移 1 步，5 插入到原 9 的位置。

这样整个的希尔排序结束，得到如上图所示的非降序序列。

算法评价

希尔排序的时间复杂度为 O(logn logn n)， 没有快速排序算法 O(n*logn)快 ，因此中等大小规模表现良好，对规模非常大的数据排序不是最优选择。

但是比直接插入排序 O(n^2）复杂度算法快得多，并且希尔排序非常容易实现，算法代码短而简单。

此外，希尔算法在最坏的情况下和平均情况下执行效率相差不是很多，与此同时快速排序在最坏 的情况下执行的效率会非常差。

专家门提倡，几乎任何排序工作在开始时都可以用希尔排序，若在实际使用中证明它不够快， 再改成快速排序这样更高级的排序算法。

代码实现

const shellSort = (A) => {
  for (let inc = ~~(A.length / 2); inc > 0; inc = ~~(inc / 2)) {
    for (let i = inc; i < A.length; i++) {
      let key = A[i]
      for (let j = i; j >= 0; j -= inc) {
        if (j - inc < 0 || A[j - inc] <= key) {
          A[j] = key
          break
        }
        A[j] = A[j - inc]
      }
    }
  }
  return A
}

相关题目

LeetCode_912 Sort an Array

LeetCode_506 Relative Ranks

总结

希尔排序算法利用分组插入排序技术，仅仅这一分组改进，减少了其复制的次数，速度要比直接插入排序快很多。当 n 值很大时数据项每一趟排序需要移动的个数很少，但数据项的距离很长。当 n 值减小时每一趟需要移动的数据增多，此时已经接近于它们排序后的最终位置。 正是这两种情况的结合才使希尔排序效率比插入排序高很多。

Shell 算法的性能与所选取的分组长度序列有很大关系。只对特定的待排序记录序列，可以准确地估算关键码的比较次数和移动次数。

想要弄清关键码比较次数和移动次数与增量选择之间的关系，并给出完整的数学分析，至今仍然是数学难题。

归并排序

5.1 归并排序

归并思想

归并排序，英文名称是 MERGE-SORT。

它是建立在归并操作上的一种有效的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。

算法的核心概念---二路归并

若将两个有序表合并成一个有序表，称为二路归并

算法过程

1. 比较 a[i] 和 b[j] 的大小，若 a[i]≤b[j]，则将第一个有序表中的元素 a[i]复制到 r[k] 中，并令 i 和 k 分别加上 1；否则将第二个有序表中的元素 b[j]复制到 r[k] 中，并令 j 和 k 分别加上 1；

2. 如此循环下去，直到其中一个有序表取完；

3. 然后再将另一个有序表中剩余的元素复制到 r 中从下标 k 到下标 t 的单元。

示例

如下图所示，初始状态时，a 序列[2,3,5]和 b 序列[2,9]为已排序好的子序列，现在利用二路归并，将 a 和 b 合并为有序序列 r，初始时，i 指向 a 的第一个元素，j 指向 b 的第一个元素，k 初始值等于 0。

说明，r 中最后一个元素起到哨兵的作用，灰色显示。

第一步，比较 a[i]和 b[j]，发现相等，如果规定相等时，a 的先进入 r，则如下图所示，i, k 分别加 1，为了形象化，归并后的元素不再绘制。

第二步，继续比较，此时 b[j]小，所以 b 的元素 2 进入 r，则如下图所示，j, k 分别加 1，

第三步，继续比较，此时 a[i]小，所以 a 的元素 3 进入 r，则如下图所示，i, k 分别加 1，

第四步，继续比较，此时 a[i]小，所以 a 的元素 5 进入 r，则如下图所示，i, k 分别加 1，此时序列 a 的 3 个元素已经归并完，b 中还剩下一个，这个可以通过 k 可以看出，它还没有到达个数 5。

第五步，将序列 b 中的所有剩余元素直接放入 r 中即可，不用做任何比较了，直至 b 变空，二路归并结束。

归并排序的算法我们通常用递归实现。

1. 先把待排序区间 [s,t] 以中点二分；
2. 接着把左边子区间排序；
3. 再把右边子区间排序；
4. 最后把左区间和右区间用一次归并操作合并成有序的区间 [s,t] 。

如下为上个例子的归并排序的完整示例，sort 和 merge 的示意图，可以看到最后一次 merge，正是上面说到的二路 [2,3,5] 和 [2,9] 的归并排序，如果不熟的，可以回过头再看看。

算法评价

归并排序的时间复杂度为 $O(nlogn)$ ，因为递归每次按照一半分区，并且 merge 需要线性时间。最重要的是该算法中最好、最坏和平均的时间性能都是 $O(nlogn)$。

归并排序的空间复杂度为 $O(n)$，会占用内存。

总之，归并排序虽然比较占用内存，但却是一种效率高且稳定的算法。

代码实现

const mergeSort = (A, start = 0, end = A.length - 1, tmpArr = A.slice()) => {
  if (start >= end) return

  const mid = ~~((end - start) / 2) + start
  mergeSort(A, start, mid, tmpArr)
  mergeSort(A, mid + 1, end, tmpArr)

  // 优化：如果两个子区间首尾元素已经有序，则没必要进行合并
  if (A[mid + 1] >= A[mid]) return A

  let left = start
  let right = mid + 1
  for (let i = start; i <= end; i++) {
    if (left === mid + 1) {
      tmpArr[i] = A[right++]
      continue
    }

    if (right === end + 1) {
      tmpArr[i] = A[left++]
      continue
    }

    if (A[left] <= A[right]) {
      tmpArr[i] = A[left++]
    } else {
      tmpArr[i] = A[right++]
    }
  }

  // 将有序结果复制给原数组
  for (let i = start; i <= end; i++) {
    A[i] = tmpArr[i]
  }
  return tmpArr
}

相关题目

剑指 Offer 51. 数组中的逆序对：在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。

315. 计算右侧小于当前元素的个数：给定一个整数数组 nums，按要求返回一个新数组  counts。数组 counts 有该性质： counts[i] 的值是   nums[i] 右侧小于  nums[i] 的元素的数量。

总结

归并排序的时间复杂度，在最坏，最好和平均都是 $O(nlogn)$，这是效率，性能非常好的排序算法。

只不过它需要占用 $O(n)$ 的内存空间，如果数据量一旦很大，内存可能吃不消，这是它的弱点和致命伤。而其他排序算法，比如快速排序，希尔排序，都是就地排序算法，它们不占用额外的内存空间。

但是归并排序作为外排序常用的手段，如果要对磁盘中的数据进行排序的话，就能派上很大用场了，比如要为 10G+的文件排序，然而内存只有 8G 甚至更小，这种时候利用归并排序不断合并排序区间，就能够有效地解决这个问题

基数排序

在讨论时假定关键码为数值型，这只是为了讨论的方便，基数排序应用的场景更可能是非数值型。

关键码位数

待排序序列中最大数的位数，例如序列 [2, 10, 8, 234]，关键码为：0,1,2,3,4,8，关键码位数 d 为 6 。如果关键码是数值型的那么上限为 10 个。

radix

关键码的取值范围，例如序列 [2, 10, 8, 234]，按照从右数的顺序第一位 d1=1 时的关键码的取值为 4,8,0,2，即范围为 0~8 。

记录数

待排序的个数

桶

基数排序中，桶的编号为关键码的取值。若关键码为数值型，则桶的编号为 0~9，共 10 个不同的桶。

分配

将记录按照某位（比如从右往左数第 1 位）将记录分配到编号为 0~10 的桶中的过程。比如 [2, 10, 8, 234]第一次分配（第一次分配定义为按照从右往左数的第 1 位）后，桶 0 中有 10，桶 2 中有 2，桶 4 中有 234，桶 8 中 8，其他桶，比如 1,3,5,6,7,9 桶中都没有记录。

收集

分配后需要对桶中的记录再串起来，这个过程叫做收集。比如，上面的序列收集后的结果为（按照从桶 0 到桶 9 的顺序收集）10, 2，234，8 。

6.1 基数排序

基数排序（radix sort），属于“分配式排序”（distribution sort）。

基数排序算法先要求计算出待排序序列的最大位数，将记录切割成不同的数字，按照最高位优先或者最低位优先的规则遍历（请看下面的注释）；

每次遍历中：

1. 分配：首先要将待排序序列中的当前位上的数字找到对应的桶；

2. 收集：分配后需要对桶中的记录再串起来，形成一个新的排序序列，供下一次分配用。

直至遍历完成，得到排序好的序列。

最高位优先 (Most Significant Digit first)法，简称 MSD 法：先按 key = 1 排序分组，再对各组按 k = 2 排序分成子组，对后面的关键码继续这样的排序分组，直到按最右位关键码 k = d 对各子组排序后。

最低位优先 (Least Significant Digit first)法，简称 LSD 法：先从 k = d 开始排序，再对 k = d-1 进行排序，依次重复，直到对 k = 1 排序后便得到一个有序序列。

示例

假定待排序的序列为 22, 33, 43, 55, 14, 28, 65, 39, 81, 33, 100 。

假定按照 LSD 法，即最低位优先原则，对以上序列进行非降序排序。

显然，这个序列的最大关键码位数为 3 。

第一次分配如下图所示，22 的最低位为 2，所以被分配到桶 2 中，33 的最低位为 3，所以被分配到桶 3 中，43 的最低位为 3，所以被分配到桶 3 中，依次类推，100 的最低位为 0，所以被分配到桶 0 中。

可以看出，桶 7 和桶 8 都没有被分配记录，所以在图中没有画出。

然后进行采集操作，采集的过程就是串联的过程，如上图所示，经过这次采集得到新序列为 100, 81, 22, 33, 43, 33, 14, 55, 65, 28, 39 。

接下来，对新序列进行第二次分配和采集，即按照从最右侧开始的第二位的顺序分配，如下图所示，此时得到的新序列为 100， 14， 22， 28，33, 33，39， 43， 55， 65， 81 。

接下来，对最新的序列进行第三次分配和采集，即按照从最右侧开始的第三位的顺序分配，如下图所示，因为一共就只有一个数 100 是 3 位数，所以其他的数都依次被分配到桶 0 中，桶 1 中含有 100 。

最后再将这些数采集起来，如下图所示，此时得到的序列为 14， 22， 28，33, 33，39， 43， 55， 65， 81， 100 。可以看到 100 的空间位置从位置 0 直接挪动到最后。

至此在这个序列中，关键码数已经等于 3，也就是说算法已经结束，我们得到了最终的排序好的非降序序列。

再想想基数排序，因为桶的顺序已经按照 0~9 顺序，按照位拆分后，每位都相当于有一个权重的大小，从最低位到最高位，权重越来越大。

可以看到相等码 33 的顺序没有发生改变，并且这并不是巧合，所以说基数排序是稳定的排序算法。

另外，因为每个桶内的元素个数是未知的，所以需要借助链表结构来实施分配时向桶内仍记录的过程。

评价

借助桶编号（键）经过多次分配和采集，最终得到一个有序序列，在这个算法排序过程中，没有经过任何记录的比较，因此基数排序是很独特的排序算法。

待排序列为 n 个记录，d 个关键码，关键码的取值范围为 radix，其中，一趟分配

时间复杂度为 $O(n)$，一趟收集时间复杂度为 $O(radix)$，共进行 d 趟分配和收集，所以链式基数排序的时间复杂度为 $O(d*(n+radix))$。

注意这不是说这个时间复杂度一定优于 $O(n*log(n))$，因为 d 的大小一般会受到 n 的影响。

采用链表或线性数组存储 n 个记录，自然地每个记录在每趟分配的时候需要临时申请一个内存空间记录下来，此时需要的空间复杂度为 $O(n)$；并且，每次分配时，每个桶中可能含有多条记录，每个桶再形成一个链表，再占用额外的内存空间 。

6.2 桶排序

桶排序和基数排序的区别在于，桶排序是按照数组中最大值和最小值来划等分，可想而知，假设对于 3 位数的情况，如果数字主要集中在 100 至 200，如果是基数排序，会创建 1 到 9 的百位桶，并不适合，没有做到均匀分布，充分利用桶空间，而桶排序就很好的优化了这一点。

但是另一方面，在判断当前元素该进入哪个桶的时候，基数排序又比桶排序有优势，所以要看情况而定

桶排序基本思路

1. 将待排序元素划分到不同的痛。先扫描一遍序列求出最大值 maxV 和最小值 minV ，设桶的个数为 k ，则把区间 [minV, maxV] 均匀划分成 k 个区间，每个区间就是一个桶。将序列中的元素分配到各自的桶。

2. 对每个桶内的元素进行排序。可以选择任意一种排序算法。

3. 将各个桶中的元素合并成一个大的有序序列。

4. 假设数据是均匀分布的，则每个桶的元素平均个数为 n/k 。假设选择用快速排序对每个桶内的元素进行排序，那么每次排序的时间复杂度为 $O(n/klog(n/k))$ 。总的时间复杂度为

当 k 接近于 n 时，桶排序的时间复杂度就可以金斯认为是 O(n) 的。即桶越多，时间效率就越高，而桶越多，空间就越大。

6.3 计数排序

计数排序是一种 $O(n)$ 的排序算法，其思路是开一个长度为 maxValue-minValue+1 的数组，然后

1. 分配。扫描一遍原始数组，以当前值- minValue 作为下标，将该下标的计数器增 1。
2. 收集。扫描一遍计数器数组，按顺序把值收集起来。

举个例子， nums=[2, 1, 3, 1, 5] , 首先扫描一遍获取最小值和最大值， maxValue=5 , minValue=1 ，于是开一个长度为 5 的计数器数组 counter ，

1. 分配。统计每个元素出现的频率，得到 counter=[2, 1, 1, 0, 1] ，例如 counter[0] 表示值 0+minValue=1 出现了 2 次。
2. 收集。 counter[0]=2 表示 1 出现了两次，那就向原始数组写入两个 1， counter[1]=1 表示 2 出现了 1 次，那就向原始数组写入一个 2，依次类推，最终原始数组变为 [1,1,2,3,5] ，排序好了。

计数排序本质上是一种特殊的桶排序，当桶的个数最大的时候，就是计数排序。

三种算法比较

其中, d 表示位数， k 在基数排序中表示 k 进制，在桶排序中表示桶的个数， maxV 和 minV 表示元 素最大值和最小值。

• 首先，基数排序和计数排序都可以看作是桶排序。

• 计数排序本质上是一种特殊的桶排序，当桶的个数取最大( maxV-minV+1 )的时候，就变成了计数排序。

• 基数排序也是一种桶排序。桶排序是按值区间划分桶，基数排序是按数位来划分；基数排序可以看做是多轮桶排序，每个数位上都进行一轮桶排序。

• 当用最大值作为基数时，基数排序就退化成了计数排序。

• 当使用 2 进制时， k=2 最小，位数 d 最大，时间复杂度 O(nd) 会变大，空间复杂度 O(n+k) 会变小。当用最大值作为基数时， k=maxV 最大， d=1 最小，此时时间复杂度 O(nd) 变小，但是空间复杂度 O(n+k) 会急剧增大，此时基数排序退化成了计数排序。

相关题目

以上快排和堆排的题也都可以用桶排，这边列举的是一个用桶排比较方便的题目，其实题解区还有不用排序的做法。大家多看看不同题解，量力而行。

1122. 数组的相对排序：给你两个数组，arr1 和  arr2，arr2  中的元素各不相同。arr2 中的每个元素都出现在  arr1  中对 arr1  中的元素进行排序，使 arr1 中项的相对顺序和  arr2  中的相对顺序相同。未在  arr2  中出现过的元素需要按照升序放在  arr1  的末尾。

621. 任务调度器：给你一个用字符数组  tasks 表示的 CPU 需要执行的任务列表。其中每个字母表示一种不同种类的任务。任务可以以任意顺序执行，并且每个任务都可以在 1 个单位时间内执行完。在任何一个单位时间，CPU 可以完成一个任务，或者处于待命状态。然而，两个相同种类的任务之间必须有长度为整数 n 的冷却时间，因此至少有连续 n 个单位时间内 CPU 在执行不同的任务，或者在待命状态。你需要计算完成所有任务所需要的最短时间 。